package com.zhanghp.class023;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/sort-an-array/
 *
 * @author zhanghp
 * @since 2024/3/16 10:05
 */
public class Code01_QuickSort {


    // 随机快速排序经典版(不推荐)
    // 如果碰到一个数组中，一个相同的数占大部分，会一直partition,导致时间会很大，不通过leetcode
    static class Solution{
        public static int[] sortArray(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return nums;
            }
            quickSort(nums, 0, nums.length - 1);
            return nums;
        }

        public static void quickSort(int[] num, int l, int r) {
            if (l >= r) {
                return;
            }
            // 随机这一下，常数时间比较大
            // 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
            int randNum = num[(int) (Math.random() * ((r - l + 1))) + l];
            int mid = partition(num, l, r, randNum);
            quickSort(num, l, mid - 1);
            quickSort(num, mid + 1, r);
        }

        // 已知arr[l....r]范围上一定有x这个值
        // 划分数组 <=x放左边，>x放右边，并且确保划分完成后<=x区域的最后一个数字是x
        public static int partition(int[] arr, int l, int r, int x) {
            int xi = 0, a = l;
            for (int i = l; i <= r; i++) {
                if (arr[i] <= x) {
                    swap(arr, i, a);
                    // swap后才能比较
                    // 否则先比较的索引，在swap，则保留的索引下标的值已经被换掉
                    if (arr[a] == x) {
                        xi = a;
                    }
                    a ++;
                }
            }
            swap(arr, --a, xi);
            return a;
        }
    }

    // 随机快速排序改进版(推荐)
    static class Solution2{

        public static int[] sortArray(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return nums;
            }
            quickSort(nums, 0, nums.length - 1);
            return nums;
        }

        public static void quickSort(int[] num, int l, int r) {
            if (l >= r) {
                return;
            }
            int randNum = num[(int) (Math.random() * ((r - l + 1))) + l];
            partition2(num, l, r, randNum);
            // 为了防止底层的递归过程覆盖全局变量
            // 这里用临时变量记录first、last
            int left = first;
            int right = last;
            quickSort(num, l, left - 1);
            quickSort(num, right + 1, r);
        }

        public static int first;
        public static int last;


        // 已知arr[l....r]范围上一定有x这个值
        // 划分数组 <x放左边，==x放中间，>x放右边
        // 把全局变量first, last，更新成==x区域的左右边界
        public static void partition2(int[] arr, int l, int r, int x) {
            first = l;
            last = r;
            int i = l;
            while (i <= last){
                if (arr[i] < x) {
                    swap(arr, first ++ , i ++ );
                }else if(arr[i] == x){
                    i ++;
                }else {
                    swap(arr, last --, i);
                }
            }
        }
    }





    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

